#import numpy


def merge(arr_0,arr_1):
  res = []
  while arr_0 and arr_1:
    min_val = arr_0.pop(0) if arr_0[0] < arr_1[0] else arr_1.pop(0)
    res.append(min_val)
  res += arr_0 if arr_0 else arr_1
  return res

def merge2(self, nums1, m: int, nums2, n: int) -> None:
  """
  Do not return anything, modify nums1 in-place instead.
  """
  nums1[m:] = nums2
  l1 = m - 1
  num = nums1[l1]
  for i in range(n):
    if nums1[-i-1] <= num:
      num = nums1.pop(l1)
      nums1.append(num)
      l1 -= 1
  return nums1

def sortArr_mrg(arr):
  _qi_arr=len(arr)
  if _qi_arr <= 1: return arr
  else:
    _liLarr = _qi_arr // 2
    arr_lef , arr_ret = sortArr_mrg(arr[:_liLarr]),\
                        sortArr_mrg(arr[_liLarr:])
    res = merge(arr_lef , arr_ret)
  return res

def build(arr, root, end):
  while True:
    child = 2 * root + 1 # 左子节点的位置
    if child > end: break# 若左子节点超过了最后一个节点，则终止循环
    if (child + 1 <= end) and (arr[child + 1] > arr[child]): child += 1 # 若右子节点在最后一个节点之前，并且右子节点比左子节点大，则我们的孩子指针移到右子节点上       
    if arr[child] > arr[root]: # 若最大的孩子节点大于根节点，则交换两者顺序，并且将根节点指针，移到这个孩子节点上
      arr[child], arr[root] = arr[root], arr[child]
      root = child
    else: break

def sortArr_hep(arr):
  n = len(arr)
  first_root = n // 2 - 1 # 确认最深最后的那个根节点的位置
  for root in range(first_root, -1, -1): # 由后向前遍历所有的根节点，建堆并进行调整
    build(arr, root, n - 1)
        
  for end in range(n - 1, 0, -1): # 调整完成后，将堆顶的根节点与堆内最后一个元素调换位置，此时为数组中最大的元素，然后重新调整堆，将最大的元素冒到堆顶。依次重复上述操作
    arr[0], arr[end] = arr[end], arr[0]
    build(arr, 0, end - 1)
  return arr

def sortArr_quc(lists,i=0,j=None):
  if j is None: j = len(lists) - 1
  if i >= j: return lists
  pivot = lists[i]
  low = i
  high = j
  while i < j:
    while i < j and lists[j] >= pivot:
      j -= 1
    lists[i]=lists[j]
    while i < j and lists[i] <=pivot:
      i += 1
    lists[j]=lists[i]
  lists[j] = pivot
  sortArr_quc(lists,low,i-1)
  sortArr_quc(lists,i+1,high)
  return lists


if __name__ == '__main__':
  import random
  random.seed(67)
  arr = [random.randint(0,100) for _ in range(10)]
  print(arr)
  print('mrg:',sortArr_mrg(arr))    # nlogn 有序子序列最好
  print('hep:',sortArr_hep(arr))    # nlogn n小不好 空 n
  print('quk:',sortArr_quc(arr))    # nlogn